package cc.wx.fom.ds;

import java.util.Collection;
import java.util.List;

/**
 * 创建于:2015年7月8日<br>
 * 无向图的接口定义
 * 
 * @author WangXue
 * @version 1.0.0
 */
public interface IUndirectedGraph {

	int getVexNum();// 返回图的顶点数

	int getEdgeNum();// 返回图的边数

	Collection<IVertex> getVertex();// 返回图的所有顶点

	Collection<IEdge> getEdge();// 返回图的所有边

//	void remove(IVertex v);// 删除一个顶点v
	
	IVertex insertVertex(String vid);
	void removeVertex(String vid);
	
	boolean containsVertex(String vid);
	/**
	 * 添加一条边
	 * 
	 * @param v1
	 *            起点id
	 * @param v2
	 *            终点id
	 */
	void insertEdge(String vid1, String vid2);
//	void remove(IEdge e);// 删除一条边e

//	void insert(IVertex v);// 添加一个顶点v
//	void insert(IEdge e);// 添加一条边e


	/**
	 * 判断顶点u、v是否邻接，即是否有边从u到v
	 * 
	 * @param u
	 * @param v
	 * @return
	 */
	boolean areAdjacent(IVertex u, IVertex v);

	/**
	 * 返回从u指向v的边，不存在则返回null
	 * 
	 * @param u
	 * @param v
	 * @return
	 */
//	IEdge edgeFromTo(IVertex u, IVertex v);

	/**
	 * 返回从u出发可以直接到达的邻接顶点
	 * 
	 * @param u
	 * @return
	 */
	List<IVertex> adjVertexs(IVertex u);

	/**
	 * 对图进行深度优先遍历
	 * 
	 * @param v
	 * @return
	 */
	List<IVertex> DFSTraverse(IVertex v);

	/**
	 * 对图进行广度优先遍历
	 * 
	 * @param v
	 * @return
	 */
	List<IVertex> BFSTraverse(IVertex v);

	/**
	 * 求顶点v到其他顶点的最短路径
	 * 
	 * @param v
	 * @return
	 */
	List<IEdge> shortestPath(IVertex v);

	List<IVertex> shortestPath(IVertex start, IVertex end);

	/**
	 * 求无向图的最小生成树
	 */
	void generateMST();

}
